import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-11-23
 * Time:16:55
 */

//使用Comparable接口
class Student implements Comparable<Student>{
    public int score;

    public Student(int score) {
        this.score = score;
    }

    @Override
    public int compareTo(Student o) {
        return this.score - o.score; //小根堆-从小到大排序
        //return o.score - this.score; //大根堆
    }

    @Override
    public String toString() {
        return score + "";
    }
}
//使用Comparator接口
//方法一：
class StudentComparator implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        return o2.score - o1.score;
    }
}
//方法二：不推荐的做法
class Student1 implements Comparator<Student1>{
    public int score;
    public Student1(int score) {
        this.score = score;
    }
    @Override
    public int compare(Student1 o1, Student1 o2) {
        return o1.score - o2.score;
    }

    @Override
    public String toString() {
        return score + "";
    }
}

//变成大根堆
class IntCmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

public class Test {

    public static void main(String[] args) {
        //Top-K问题
        Top_K top_k = new Top_K();
        int[] array = {1,3,5,7,2,4,6,8};
        //求前k个最小元素
        //整体建立一个大小为N的小根堆做法
        int[] ret = top_k.smallestK1(array,4);
        System.out.println("前K个最小的元素为：" + Arrays.toString(ret));//[1, 2, 3, 4]

        //将前k个元素建大根堆的做法
        int[] ret1 = top_k.smallestK(array,4);
        System.out.println("前K个最小的元素为：" + Arrays.toString(ret1));//[4, 3, 2, 1]

        //求前k个最大元素
        //整体建立一个大小为N的大根堆做法
        int[] ret2 = top_k.bigestK1(array,4);
        System.out.println("前K个最大的元素为：" + Arrays.toString(ret2));//[8, 7, 6, 5]

        //将前k个元素建小根堆的做法
        int[] ret3 = top_k.bigestK(array,4);
        System.out.println("前K个最大的元素为：" + Arrays.toString(ret3));//[5, 6, 7, 8]

        //第K个最小的元素
        int num = top_k.the_K_smallest(array,4);
        System.out.println("第K个最小的元素为：" + num);//4

        //第K个最大的元素
        int num1 = top_k.the_K_biggest(array,4);
        System.out.println("第K个最大的元素为：" + num1);//5
    }

    public static void main3(String[] args) {
        //Java默认PriorityQueue是小根堆,想要将其变成大根堆，那么需要创建一个实现了Comparator接口的类，然后让该类去重写compare抽象方法
        //以Integer类为例，Integer类实现了Comparable接口，重写了compareTo方法，其中定义了自然顺序（从小到大），不可改变，通过创建一个
        //实现了Comparator(用于自定义排序规则)接口的类来反转Integer的自然排序顺序，从而达到大根堆的效果
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());
        priorityQueue.offer(11);
        priorityQueue.offer(12);

        System.out.println(priorityQueue.peek());//12
    }
    public static void main2(String[] args) {
        //PriorityQueue的构造方法

        //创建一个空的优先级队列，底层默认容量是11
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        //创建一个空的优先级队列，底层的容量为initialCapacity(这里是100)
        PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>(100);

        //用ArrayList对象来构造一个优先级队列的对象(ArrayList实现了Collection接口)
        ArrayList<Integer> list = new ArrayList<>();
        list.add(2);
        list.add(1);
        list.add(4);
        PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(list);
        System.out.println(priorityQueue2.size());//3
        System.out.println(priorityQueue2.peek());//1
    }
    public static void main1(String[] args) {
        //Queue<Integer> priorityQueue = new PriorityQueue<>();

        //PriorityQueue在Java中默认是一个小根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(10);
        priorityQueue.offer(20);
        priorityQueue.offer(3);

        System.out.println(priorityQueue.peek());//3 - 获取的堆顶元素是3，说明默认是一个小根堆

        //不能插入null对象，否则会抛出NullPointerException
        //priorityQueue.offer(null);//错误

        //PriorityQueue中放置的元素必须要能够比较大小，否则会抛异常ClassCastException
        //因为优先级队列中的元素是要比较大小的，也就是说它的元素的类型必须是实现Comparable接口的(例如Integer)，否则会有异常
        //就像自定义的Student类，想要它可以作为PriorityQueue的参数，必须让Student类实现Comparable接口(自然排序) 或者
        //Comparator接口(自定义排序)，然后重写compareTo或者compare抽象方法
        PriorityQueue<Student> priorityQueue1 = new PriorityQueue<>();
        priorityQueue1.offer(new Student(85));
        priorityQueue1.offer(new Student(60));

        System.out.println(priorityQueue1.poll());//60

        //2 推荐做法
        PriorityQueue<Student> priorityQueue2 = new PriorityQueue<>(new StudentComparator());
        priorityQueue2.offer(new Student(55));
        priorityQueue2.offer(new Student(72));

        System.out.println(priorityQueue2.peek());//72

        //不推荐的做法
        //PriorityQueue无参构造默认是Comparable接口比较，想要变成Comparator接口比较，
        //就得传有参的构造方法，即一个Comparator接口的实例，告诉PriorityQueue要使用Comparator接口
        //如果是上面2的做法，就不需要这么麻烦
        PriorityQueue<Student1> priorityQueue3 = new PriorityQueue<>(new Student1(0));
        priorityQueue3.offer(new Student1(1));
        priorityQueue3.offer(new Student1(2));

        System.out.println(priorityQueue3.peek());//1
    }
}
